package Leetcode.Dichotomy;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: kirito
 * @Date: 2024/4/7 14:41
 * @Description:
 * 最小体力消耗路径
 * 你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费 体力 最小的一条路径。
 *
 * 一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。
 *
 * 请你返回从左上角走到右下角的最小 体力消耗值 。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：heights = [[1,2,2],[3,8,2],[5,3,5]]
 * 输出：2
 * 解释：路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。
 * 这条路径比路径 [1,2,2,2,5] 更优，因为另一条路径差值最大值为 3 。
 * 示例 2：
 *
 *
 *
 * 输入：heights = [[1,2,3],[3,8,4],[5,3,5]]
 * 输出：1
 * 解释：路径 [1,2,3,4,5] 的相邻格子差值绝对值最大为 1 ，比路径 [1,3,5,3,5] 更优。
 * 示例 3：
 *
 *
 * 输入：heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
 * 输出：0
 * 解释：上图所示路径不需要消耗任何体力。
 *
 *
 * 提示：
 *
 * rows == heights.length
 * columns == heights[i].length
 * 1 <= rows, columns <= 100
 * 1 <= heights[i][j] <= 106
 */

public class minimumEffortPath {
    int[][] dirs = {{-1, 0},
                    {1, 0},
                    {0, -1},
                    {0, 1}}; // 定义四个方向的移动，分别为上、下、左、右

    public int minimumEffortPath(int[][] heights) { // 最小努力路径函数
        int m = heights.length; // 获取矩阵的行数
        int n = heights[0].length; // 获取矩阵的列数
        int left = 0, right = 999999, ans = 0; // 初始化最小努力值left和right，以及答案ans
        while (left <= right) { // 二分查找
            int mid = (left + right) / 2; // 计算中间值
            Queue<int[]> queue = new LinkedList<int[]>(); // 初始化队列
            queue.offer(new int[]{0, 0}); // 起点入队
            boolean[] seen = new boolean[m * n]; // 初始化一个标记数组，用于记录是否访问过某个位置
            seen[0] = true; // 起始位置标记为已访问
            while (!queue.isEmpty()) { // 广度优先搜索
                int[] cell = queue.poll(); // 取出队首元素
                int x = cell[0], y = cell[1]; // 获取当前位置
                for (int i = 0; i < 4; ++i) { // 四个方向遍历
                    int nx = x + dirs[i][0]; // 计算新位置的横坐标
                    int ny = y + dirs[i][1]; // 计算新位置的纵坐标
                    if (nx >= 0 &&
                        nx < m &&
                        ny >= 0 &&
                        ny < n &&
                        !seen[nx * n + ny] &&
                        Math.abs(heights[x][y] - heights[nx][ny]) <= mid) { // 检查新位置是否在范围内，且高度差是否小于等于mid
                        queue.offer(new int[]{nx, ny}); // 若满足条件，则将新位置入队
                        seen[nx * n + ny] = true; // 标记新位置为已访问
                    }
                }
            }
            if (seen[m * n - 1]) { // 如果终点被访问过，说明mid是可行的最小努力值
                ans = mid; // 更新答案
                right = mid - 1; // 缩小搜索范围
            } else {
                left = mid + 1; // 如果不满足，则增大搜索范围
            }
        }
        return ans; // 返回最小努力值
    }

}
